package leetcode.code0407;

import java.util.PriorityQueue;

public class Solution1 extends Solution407 {

	private PriorityQueue<int[]> edge;
	private int x;
	private int y;
	boolean[][] check;

	@Override
	public int trapRainWater(int[][] heightMap) {
		x = heightMap.length;
		y = heightMap[0].length;
		check = new boolean[x][y];
		edge = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
		fillEdge(heightMap);
		int ans = 0;
		while (!edge.isEmpty()) {
			int[] low = edge.poll();
			ans += infectFrom(heightMap, low[0], low[1], heightMap[low[0]][low[1]]);
		}
		return ans;
	}

	private int infectFrom(int[][] heightMap, int x, int y, int low) {
		int row = 0;
		int col = 0;
		int ans = 0;
		if (this.canBeInfect(row = x + 1, col = y)) {
			ans += this.infectHere(heightMap, row, col, low);
		}
		if (this.canBeInfect(row = x - 1, col = y)) {
			ans += this.infectHere(heightMap, row, col, low);
		}
		if (this.canBeInfect(row = x, col = y + 1)) {
			ans += this.infectHere(heightMap, row, col, low);
		}
		if (this.canBeInfect(row = x, col = y - 1)) {
			ans += this.infectHere(heightMap, row, col, low);
		}
		return ans;
	}

	private int infectHere(int[][] heightMap, int row, int col, int low) {
		int ans = 0;
		int height = 0;
		if ((height = heightMap[row][col]) < low) {
			ans += (low - height);
			ans += this.infectFrom(heightMap, row, col, low);
		} else {
			edge.add(new int[] { row, col, heightMap[row][col] });
		}
		return ans;
	}

	private boolean canBeInfect(int row, int col) {
		if (row >= 0 && col >= 0 && row < x && col < y && !check[row][col]) {
			check[row][col] = true;
			return true;
		}
		return false;
	}

	private void fillEdge(int[][] heightMap) {
		for (int i = 0; i < y - 1; i++) {// 上
			edge.add(new int[] { 0, i, heightMap[0][i] });
			check[0][i] = true;
		}
		for (int i = 0; i < x - 1; i++) {// 右
			edge.add(new int[] { i, y - 1, heightMap[i][y - 1] });
			check[i][y - 1] = true;
		}
		for (int i = y - 1; i > 0; i--) {// 下
			edge.add(new int[] { x - 1, i, heightMap[x - 1][i] });
			check[x - 1][i] = true;
		}
		for (int i = x - 1; i > 0; i--) {
			edge.add(new int[] { i, 0, heightMap[i][0] });
			check[i][0] = true;
		}
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
	}

}
